package algotithm.leetcode.dp.test1186;

/**
 * @author 25068
 * @Date 2021/5/4 11:04
 * @Title 1186. 删除一次得到子数组最大和
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1,-2,-2,3};
        int sum = solution.maximumSum(arr);
        System.out.println(sum);
    }

    public int maximumSum(int[] arr) {
        int n = arr.length;
        int k = 1;
        int max = arr[0];
        int[][] dp = new int[n][k + 1];
        //init
        dp[0][0] = arr[0];
        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i],arr[i]);
            max = Math.max(max,dp[i][0]);
        }
        //dp
        for(int i = 1; i < n; i++){
            for(int j = 1; j <= k; j++){
                dp[i][j] = Math.max(dp[i - 1][j] + arr[i],dp[i - 1][j - 1]);
                max = Math.max(max,dp[i][j]);
            }
        }

        return max;
    }
}
